#include <iostream>
#include <vector>
#include <cmath>
#include <limits>

using namespace std;

// 定义飞行线的结构体
struct FlightLine
{
    int id;                // 飞行线ID
    double x1, y1, x2, y2; // 飞行线的两个端点坐标
};

// 定义查询点的结构体
struct QueryPoint
{
    double x, y; // 查询点坐标
};

// 计算点到线段的最短距离
double pointToLineDistance(double px, double py, double x1, double y1, double x2, double y2)
{
    double dx = x2 - x1;
    double dy = y2 - y1;
    double lineLengthSq = dx * dx + dy * dy; // 线段长度的平方

    if (lineLengthSq == 0)
    {
        // 如果线段长度为0，返回点到点的距离
        return sqrt((px - x1) * (px - x1) + (py - y1) * (py - y1));
    }

    // 计算投影参数 t
    double t = ((px - x1) * dx + (py - y1) * dy) / lineLengthSq;
    t = max(0.0, min(1.0, t)); // 限制 t 在 [0, 1] 之间

    // 计算投影点坐标
    double projectionX = x1 + t * dx;
    double projectionY = y1 + t * dy;

    // 返回点到投影点的距离
    return sqrt((px - projectionX) * (px - projectionX) + (py - projectionY) * (py - projectionY));
}

// 暴力方法求解最近飞行线
vector<int> findNearestFlightLine(const vector<FlightLine> &flightLines, const vector<QueryPoint> &queryPoints)
{
    vector<int> results;
    for (const auto &qp : queryPoints)
    {
        double minDistance = numeric_limits<double>::max();
        int nearestLineId = -1;

        for (const auto &line : flightLines)
        {
            double distance = pointToLineDistance(qp.x, qp.y, line.x1, line.y1, line.x2, line.y2);
            if (distance < minDistance)
            {
                minDistance = distance;
                nearestLineId = line.id;
            }
        }

        results.push_back(nearestLineId);
    }
    return results;
}

int main()
{
    int numTestCases; // 测试用例的数量
    cout << "请输入测试用例的数量: ";
    cin >> numTestCases;

    for (int t = 1; t <= numTestCases; ++t)
    {
        cout << "\n=== 测试用例 " << t << " ===" << endl;

        // 输入飞行线数据
        int numFlightLines;
        cout << "请输入飞行线的数量: ";
        cin >> numFlightLines;

        vector<FlightLine> flightLines(numFlightLines);
        for (int i = 0; i < numFlightLines; ++i)
        {
            cout << "请输入飞行线 " << i + 1 << " 的两个端点坐标 (x1 y1 x2 y2): ";
            cin >> flightLines[i].x1 >> flightLines[i].y1 >> flightLines[i].x2 >> flightLines[i].y2;
            flightLines[i].id = i + 1; // 飞行线ID从1开始
        }

        // 输入查询点数据
        int numQueryPoints;
        cout << "请输入查询点的数量: ";
        cin >> numQueryPoints;

        vector<QueryPoint> queryPoints(numQueryPoints);
        for (int i = 0; i < numQueryPoints; ++i)
        {
            cout << "请输入查询点 " << i + 1 << " 的坐标 (x y): ";
            cin >> queryPoints[i].x >> queryPoints[i].y;
        }

        // 计算最近飞行线
        vector<int> results = findNearestFlightLine(flightLines, queryPoints);

        // 输出结果
        cout << "\n测试用例 " << t << " 的结果:" << endl;
        for (size_t i = 0; i < results.size(); ++i)
        {
            cout << "查询点 " << i + 1 << " 的最近飞行线ID是: " << results[i] << endl;
        }
    }

    return 0;
}